Math 512: Finite Model Theory 0-1 Laws Constant p

John Baldwin

March 4, 1997

References: Vaananen Chapter 5, E and F Chapter 3, E.M. Palmer Graphical Evolution, Wiley 1985, QA 166.17, Feller

0.1 Example. A (round robin) tournament is a directed graph with an edge between every pair of points.

Fix k. Is there a tournament such that for each set of k-players there is another who beats each of them?

0.2 Definition. Let Ω be a finite sample space with a probability measure P. (i.e. for each G ∈ Ω, 0 ≤ P (G) ≤ 1 and ∑_{G∈Ω} P (G) = 1.)

1. An event is a subset of Ω.

2. A random variable is a map X from Ω to the reals.

3. E(X), the expected value of X is ∑_{G∈Ω} X(G)P (G)

Note that for any random variable X, Y, any reals a, b,

E(aX + bY) = aE(X) + bE(Y).

We will find the following inequality of Markov very useful. The proof is immediate from the definition.

0.3 Lemma. If X ≥ 0 and t > 0,

P (X ≥ t) ≤ E(X)/t.

Returning to the original example, let S_{n} be the set of all tournaments with n players. |S_{n}| = 2^{\binom{n}{2}}. Each of these is equally likely.

Call a k-set X bad if no element dominates each member of X. Let Y (T) be the number of bad k-sets in a tournament T and P_{n}(Y ≥ m) be the probability that a tournament of size n contains at least m bad k-sets. (The subscript n would usually be omitted; we write it once for emphasis.)

E_{n}(Y) = \binom{n}{k}(1 − (1/2)^{k})^{n−k}.

(Why? Let, for i < \binom{n}{k}, Y_{i} be a random variable which is 1 if the ith k-tuple is bad, and 0 otherwise. Then E(Y) = \binom{n}{k}E(Y_{i}) and each E(Y_{i}) = (1 − (1/2)^{k})^{n−k}.

Then E_{n}(Y) → 0 and by Markov’s inequality P_{n}(Y ≥ 1) → 0. So a.a., there is such a tournament.

Now we move to a more general situation. Fix a finite relational vocabulary τ. Let K_{n} be the collection of all structures with universe n. These are the labeled τ structures of size n.

Simplest probability measure: for any X ⊆ K_{n}: P_{n}(X) = |X|/|K_{n}|. For a global relation ϕ, P_{n}(ϕ) = P_{n}({A : A ∈ K_{n} ∧ A ⊧ ϕ}.

Consider graphs: What is P_{n}(even), P_{n}(connected), P_{n}(planar)

For simplicity we will restrict our consideration to graphs; the extension to arbitrary finite symmetric relational languages (R(\overline{x}) → R(\overline{x}′) for any permutation of \overline{x}) is basically by complication of notation.

0.4 Definition. Uniform Distribution: For any structures A, B with size n, P_{n}(A) = P_{n}(B). For a global relation ϕ, P (ϕ) = lim_{n→∞} P_{n}(ϕ) if this limit exists.

0.5 Lemma. For graphs the uniform distribution is given locally by for any a, b ∈ A, the probability of an edge between a and b is 1/2.

Proof. P_{n}(A) = (1/2)^{k} · (1 − 1/2)^{\binom{n}{2}−k} = (1/2)^{\binom{n}{2}} where k is the number of edges in A.

0.6 Definition. A class of global relations, e.g. the sentences in a logic L, satisfy the 0-1 law if for every ϕ ∈ L either lim_{n→∞ϕ} = 1 or lim_{n→∞ϕ} = 0.

0.7 Theorem. The 0-1-law holds for first order logic under the uniform distribution.

Let K_{0} be the set of all finite graphs. Write A ≤ B if A is a substructure of B. We will later abstract to a more general treatment of ‘strong’ submodels; we also say A is closed in B.

0.8 Definition. The class K of finite τ-structures with the relation ≤ satisfies the ≤- amalgamation property, if for any A, B_{1}, B_{2} ∈ K such that A ≤ B_{1}, A ≤ B_{2} there is a structure D ∈ K and an isomorphic embedding f : B_{2} → D such that B_{1} ≤ D and f(B_{2}) ≤ D, f | A = id_{A}. The structure D is called the amalgamation of B_{1} and B_{2} over A.

0.9 Definition. The model M is called (K, ≤)-homogeneous-universal (h.u.) or (K, ≤)- generic if it satisfies following conditions:

1. If A ≤ M, A ≤ B ∈ K, then there exists B ≤ M such that B ≃ =_{A} B,

2. If X is a finite subset of M, there is a finite X̄ with X ⊆ X̄ ≤ M.

0.10 Lemma. If K satisfies the ≤-amalgamation property then there is a (K, ≤)-generic model that is unique up to isomorphism.

Proof. Construct a family of finite structures ⟨A_{n} : n < ω⟩. To construct A_{n+1} consider all pairs ⟨B_{i}, C_{i}⟩ such that B_{i} ⊆ A_{n}, B_{i} ≤ A_{n}, B_{i} ≤ C_{i} and |C_{i}| ≤ n. Construct A_{n,j+1} by amalgamating A_{n,j} and C_{j} over B_{j}. Note that ∪_{n<ω}A_{n} is as required. For the isomorphism construct a back and forth.

0.11 Notation. Consider the special case of graphs. Let ϕ_{k} denote the sentence which asserts that there are two sets of size k and an element related to each member of the first set and none of the second. These are called the extension axioms. We call the consequences of the extension axioms T_{ran}.

Noting that in the case of graphs we can build the back-and-forth one element at a time (all substructures are strong substructures), we have:

0.12 Lemma. The generic model G_{ran} for ⟨K_{0}, ≤⟩, is the unique countable model for the extension axioms. Thus, the extension axioms axiomatize a complete (ℵ_{0}-categorical) decidable theory.

0.13 Theorem. Let the edge probability be p. For each extension axiom ϕ_{k}, lim_{n→∞ϕ_{k}} = 1.

Proof. A pair of k-element sets (S, T) is said to be bad (in a graph G) if there is no g ∈ G which is related to every element of S and not related to any element of T. Let X(G) be the number of bad pairs in G (|G| = n).

E_{n}(X) = \binom{n}{2k}\binom{2k}{k}(1 − p^{k}(1 − p)^{k})^{n−2k}.

As before E_{n}(X) → 0 so P_{n}(X ≥ 1) → 0. Thus P_{n}(ϕ_{k}) → 1.

0.14 Definition. A theory T is quantifier eliminable if for every formula ψ(\overline{x}) there is a quantifier free formula θ(\overline{x}) such that

T ⊧ (∀\overline{x})[ψ(\overline{x}) ↔ θ(\overline{x})].

Using the saturation and genericity of the random graph we have a very soft proof of: 0.15 Corollary. T_{ran} is quantifier eliminable.

Further corollaries: 0.16 Corollary. 1. The collection of sentences ϕ such that P (ϕ) = 1 is decidable.

2. The global relation ‘|A| is a prime’ is not first order axiomatizable.

3. Every sentence true in the random graph has a finite model, i.e. T_{ran} has the finite

model property. 0.17 Definition. The spectrum of sentence ϕ is {n : (∃A)A ⊧ ϕ ∧ |A| = n}.

Problems: Fix ϕ with spectrum equal to all prime powers, to all primes?

Very open problem: Is the complement of a spectrum necessarily a spectrum? Lemma 0.18 (Fagin). For any first order ϕ either ϕ or ¬ϕ has co-finite spectrum.

Proof. For some N, either for all n > N, P_{n}(ϕ) > 1/2 or for all n > N, P_{n}(¬ϕ) > 1/2.